home *** CD-ROM | disk | FTP | other *** search
/ SuperHack / SuperHack CD.bin / CODING / MISC / ALGORITM.ZIP / ALGORITM.TXT
Encoding:
Text File  |  1996-03-16  |  3.3 KB  |  129 lines
  1. -------------------------------------------------------------------------------
  2. Algorithm:      Quicksort
  3. O(f(n)):        A(n)=n*lg(n)
  4. ..W(n)=n^2 (sorted!)
  5. In-place:       No.
  6. Call:           Quicksort(left,right,arr)
  7. ...
  8. Code:
  9. .Quicksort(left,right:integer;var arr:array[left..right] of integer);
  10. .  var m,i,j:integer;
  11. .begin
  12. .  i:=left;
  13. .  j:=right;
  14. .  m:=arr[trunc((left+right)/2)]; (* arr[left],arr[right],... *)
  15. .  repeat
  16. .    while (arr[i]<m) do i:=i+1;
  17. .    while (arr[j]>m) do j:=j-1;
  18. .    if (i<=j) then begin
  19. .      swap(arr[i],arr[j]);
  20. .      i:=i+1;
  21. .      j:=j-1;
  22. .    end;
  23. .  until (i>j);
  24. .  if (left<j)  then Quicksort(left,j,arr);
  25. .  if (i<right) then Quicksort(i,right,arr);
  26. .end;
  27.  
  28. -------------------------------------------------------------------------------
  29. Algorithm:      Shellsort
  30. O(f(n)):        A(n)=
  31. ..W(n)=n^1.5
  32. In-place:       Yes
  33. Call:           Shellsort(n,arr)
  34.  
  35. Code:
  36. .Shellsort(n:integer;var arr:array[1..n] of integer);
  37. .  var d,i,j:integer;
  38. .      flag:boolean;
  39. .begin
  40. .  d:=n-1;
  41. .  while (d >= 1) do begin
  42. .    for i:=1 to n-d do begin
  43. .      j:=i;
  44. .      flag:=true;
  45. .      while flag do begin
  46. ..flag:=false;
  47. ..if (j>=1) then 
  48. ..  if (arr[j]>arr[j+d]) then begin
  49. ..    swap(arr[j],arr[j+d]);
  50. ..    flag:=true;
  51. ..    j:=j-d;
  52. ..  end;
  53. .      end;
  54. .    end;
  55. .    d:=trunc(d/2);
  56. .  end;
  57. .end;
  58.  
  59. -------------------------------------------------------------------------------
  60. Algorithm:      Mergesort
  61. O(f(n)):        A(n)=n*lg(n)
  62. ..W(n)=n*lg(n)
  63. In-place:       No
  64. Call:           Mergesort(left,right,arr)
  65.  
  66. Code:
  67. .Mergesort(left,right:integer;var arr:array[left..right] of integer);
  68. .  var middle:integer;
  69. .begin
  70. .  if (left < right) then begin
  71. .    middle:=trunc((left+right)/2);
  72. .    Mergesort(left,middle,arr);
  73. .    Mergesort(middle+1,right,arr);
  74. .    Merge(left,middle,middle+1,right,arr);
  75. .  end;
  76. .end;
  77.  
  78. -------------------------------------------------------------------------------
  79. Algoritm:       Heapsort
  80. O(f(n)):        A(n)=n*lg(n)
  81. ..W(n)=2*(n-1)*lg(n)
  82. In-place:       Yes
  83. Call:           Heapsort(n,arr)
  84.  
  85. Code:
  86. .Heapsort(n:integer;var arr:array[1..n] of integer);
  87. .  var i,heapsize,max:integer;
  88.  
  89. .  fixheap(lower,element,upper:integer);
  90. .  (* Reestablish the heap property in the tree, the element to insert
  91. .     at position 'lower' is 'element',last index in heap is 'upper'.
  92. .     The heap property means that the element at index 'lower' should
  93. .     be the largest in the subtree it represents.
  94. .   *)
  95.  
  96. .begin
  97.  
  98. .  (* heap construction *)
  99. .  for i:=trunc(n/2) to 1 step -1 do fixheap(i,arr[i],n);
  100.  
  101. .  (* rearrange *)
  102. .  for heapsize:=n to 2 step -1 do begin
  103. .    max:=arr[1];
  104. .    fixheap(1,arr[heapsize],heapsize-1);
  105. .    arr[heapsize]:=max;
  106. .  end;
  107.  
  108. .end;
  109.  
  110. -------------------------------------------------------------------------------
  111. Algoritm:       Cardshuffling
  112. O(f(n)):        A(n)=n
  113. ..W(n)=n
  114. In-place:       Yes
  115. Call:           Shuffle(n,arr)
  116.  
  117. Code:
  118. .Shuffle(n:integer;var arr:array[1..n] of integer)
  119. .  var i,j:integer;
  120. .begin
  121. .  for i:=1 to n step  1 do arr[i]:=i; (* initiera *)
  122. .  for i:=n to 1 step -1 do begin      (* do the shuffling *)
  123. .    j:=trunc(i*rnd)+1;
  124. .    swap(arr[j],arr[i]);
  125. .  end;
  126. .end;
  127.  
  128. -------------------------------------------------------------------------------
  129.